package com.zlk.algorithm.algorithm.tools.slidingWindow049;

import org.junit.Test;

import java.util.Arrays;

// 无重复字符的最长子串
// 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
// 测试链接 : https://leetcode.cn/problems/longest-substring-without-repeating-characters/
public class Code02_LongestSubstringWithoutRepeatingCharacters {

    @Test
    public void test(){
        System.out.println(lengthOfLongestSubstring("abcabcbb"));
    }

    // 滑动窗口向右滑动，r向右滑动，当前chars[r] 加入窗口中去，得判断加入得字符是否在窗口中出现
    // 如何判断在窗口中出现，得提前建立索引表，记录字符上次出现得位置，如果出现得位置是在l 之前得也就是不在窗口中，那么可以加入
    // 如果是大于l得话那就是在窗口中，这样l位置需要移动到窗口中已经出现得位置得后一位
    public int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();
        int[] hash =new int[256];
        Arrays.fill(hash,-1);
        int ans = Integer.MIN_VALUE;
        int sum=0;
        for (int l = 0,r=0; r < chars.length; r++) {
            if(hash[chars[r]]<l){//窗口内不存在
                sum++;
            }else{
                //存在重复
                ans = Math.max(ans,sum);
                l=hash[chars[r]]+1;
                sum = r-l+1;
            }
            //跟新位置
            hash[chars[r]] = r;
        }
        return Math.max(ans,sum);
    }

}
